package com.leetCode;

/**
 * Description: 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-10-27 14:16:59
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-10-27     张李鑫                     1.0         1.0 Version
 */
public class MaxSubArray {

    /**
     * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     *
     * @param nums
     * @return
     */
    public static int maxSubArray(int[] nums) {
        return process(nums, 0, nums.length - 1);
    }

    public static int process(int[] arr, int start, int end) {
        if (end <= start) {
            return 0;
        }
        //不选择当前
        int p1 = arr[start] + process(arr, start + 1, end);
        //不选最后
        int p2 = arr[end] + process(arr, start, end - 1);
        return Math.max(p1, p2);

    }

    public static void main(String[] args) {
        int[] arr = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};

        System.out.println(maxSubArray(arr));
    }
}
